package com.atguigu.algorithm.sort;

import java.util.Arrays;

/**
 * 基数排序（桶排序）
 * 此版只适用于正数
 * 基数排序是空间换时间的经典算法
 *
 * @author xr-8
 * @date 2022-09-12
 * @time 19:50
 */
public class RadixSort {

    public static void main(String[] args) {
//        int arr[] = {5, 0, 7, 4, 10, 1};
//        int arr[] = {1, 2, 3, 4, 5, 6};
//        int arr[] = {2, 1, 3, 4, 5, 6};
        int arr[] = {34, 8434, 12, 3, 11, 6, 12, 980};
        sort(arr);
    }

    public static void sort(int[] arr) {
        // 1、获取数组中的最大数值的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();
        // 2、放入桶中
        // 2.1 定义桶
        int[][] bucket = new int[10][arr.length];
        // 2.2 定义10个桶存放的元素个数，包括后面的从桶中取出数字，需要基于此数组的值
        int[] bucketNum = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) { // 最大值有几位就循环多少次
            for (int j = 0; j < arr.length; j++) {
                int position = arr[j] / n % 10; // 获取相应位数的数字
                bucket[position][bucketNum[position]] = arr[j];
                bucketNum[position]++;
            }

            // 3、再从桶中取出数字放入原数组中
            int newLength = 0;
            for (int j = 0; j < bucketNum.length; j++) {
                if (bucketNum[j] > 0) {
                    for (int k = 0; k < bucketNum[j]; k++) {
                        arr[newLength++] = bucket[j][k];
                    }
                    bucketNum[j] = 0; // 取完后清零
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
